package com.atguigu.dp;

public class P198 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,1};//{2,7,9,3,1};
        System.out.println(maxMoney(arr));
    }

    private static int max = 0 ;
    private static int maxMoney(int[] arr) {

        if(arr.length==1){
            return arr[0];
        }
        if(arr.length==2){
            return Math.max(arr[0],arr[1]);
        }
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0],arr[1]);

        for(int i = 2;i<arr.length ; i++){
            dp[i] = Math.max(dp[i-2]+arr[i],dp[i-1]) ;
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}
